{
 "cells": [
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "# Maximum In A Stack\n",
    "\n",
    "[The Original Question](https://mp.weixin.qq.com/s/VwnP3YdNhi7CvMUalh9Tyw)"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "## Question\n",
    "\n",
    "Implement a class for a stack that supports all the regular functions (such as `push()` and `pop()`) and an additional function `max()` which returns the maximum element in the stack (return `None` if the stack is empty). Each method should run in constant time."
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 1,
   "metadata": {},
   "outputs": [],
   "source": [
    "class MaxStack:\n",
    "    def __init__(self):\n",
    "        self.data_stack = []\n",
    "        self.max_stack = []\n",
    "    \n",
    "    def push(self, value):\n",
    "        self.data_stack.append(value)\n",
    "        if self.max_stack == [] or self.max_stack[-1] <= value:\n",
    "            self.max_stack.append(value)\n",
    "        else:\n",
    "            self.max_stack.append(self.max_stack[-1])\n",
    "    \n",
    "    def pop(self):\n",
    "        self.data_stack.pop()\n",
    "        self.max_stack.pop()\n",
    "    \n",
    "    def maximum(self):\n",
    "        if self.max_stack == []:\n",
    "            return None\n",
    "        else:\n",
    "            return self.max_stack[-1]"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 2,
   "metadata": {},
   "outputs": [
    {
     "name": "stdout",
     "output_type": "stream",
     "text": [
      "3\n",
      "2\n"
     ]
    }
   ],
   "source": [
    "s = MaxStack()\n",
    "s.push(1)\n",
    "s.push(2)\n",
    "s.push(3)\n",
    "s.push(2)\n",
    "print(s.maximum())\n",
    "s.pop()\n",
    "s.pop()\n",
    "print(s.maximum())"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "## Notes\n",
    "\n",
    "In *Python*, type `list` provides functions that use `list` as a stack. At the same time, *Python* build-in function `max()` can also apply to a `list`. These functions can make this question meaningless.\n",
    "\n",
    "```python3\n",
    "class MaxStack:\n",
    "    def __init__(self):\n",
    "        self.stack = []\n",
    "    \n",
    "    def push(self, value):\n",
    "        self.stack.append(value)\n",
    "    \n",
    "    def pop(self):\n",
    "        self.stack.pop()\n",
    "    \n",
    "    def maximum(self):\n",
    "        return max(self.stack)\n",
    "```\n",
    "\n",
    "On the other hand, if we try to finish all the tasks from making definions of a `Node`, a `Linked_Stack` to a `Max_Stack` (which is what we need), the efforts is horrible. It IS a way to solve the question, but the most complicate one.\n",
    "\n",
    "The executable code above only shows the core of the algorithm. If you have other methods, try it on your own!"
   ]
  }
 ],
 "metadata": {
  "kernelspec": {
   "display_name": "Python 3",
   "language": "python",
   "name": "python3"
  },
  "language_info": {
   "codemirror_mode": {
    "name": "ipython",
    "version": 3
   },
   "file_extension": ".py",
   "mimetype": "text/x-python",
   "name": "python",
   "nbconvert_exporter": "python",
   "pygments_lexer": "ipython3",
   "version": "3.7.3"
  }
 },
 "nbformat": 4,
 "nbformat_minor": 4
}
